#define _CRT_SECURE_NO_WARNINGS


#include"Sort.h"

void TestInsertSort()
{
	int a[5] = { 5, 2, 1, 4, 3 };
	int sz = sizeof(a) / sizeof(a[0]);

	InsertSort(a, sz);

	PrintArray(a, sz);
}

void BubbleSortTest()
{
	int a[5] = { 5, 2, 1, 4, 3 };
	int sz = sizeof(a) / sizeof(a[0]);

	BubbleSort(a, sz);

	PrintArray(a, sz);
}

void SelectSortTest()
{
	int a[5] = { 5, 2, 1, 4, 3 };
	int sz = sizeof(a) / sizeof(a[0]);

	SelectSort(a, sz);

	PrintArray(a, sz);
}

void ShellSortTest()
{
	//int a[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1 };
	int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	ShellSort(a, sz);

	PrintArray(a, sz);
}

void QuickSortTest()
{
	int a[] = { 5, 2, 3, 1 };

	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	QuickSort(a, 0, sz - 1);

	PrintArray(a, sz);
}

void QuickSortNonRTest()
{
	int a[] = { -7087,12694,-19352,-7660,12052,-11316,-352,18321,15,19967,6331,-1289,6540,-10454,-19309,-10193,15074,8926,510,-11044,5156,10397,18477,7011,-16822,-8281,-13675,-14616,11103,-3338,1597,-10313,15808,16242,11438,19029,-3969,-5137,6955,-11426,11283,-9429,15512,5109,-16951,9741,7024,7374,-1429,-3822,16494,11183,13581,-624,-8692,9033,13253,-6781,-8030,-12564,-6495,-8075,6375,-7638,-8894,-15126,6196,7565,-8335,17298,15965,-10424,-11440,115,-15303,-8185,-14136,-4704,5078,19498,-8636,19068,1950,1980,-19147,1634,-634,5704,-16161,-19512,18818,1598,-13237,-4924,8819,-17508,-6143,-922,-1262,5676,-7286,19153,17772,12016,7017,-3883,10757,-5870,-4128,17396,17387,14927,11939,19301,13760,16166,15332,10975,-5162,-19353,9945,-295,-13588,-1908,-13244,-348,-12064,10565,913,-16781,16214,-1846,7727,5283,10492,-2839,15925,-7995,12903,-9995,-9204,-15275,-9845,-3452,19892,-1347,-3371,11224,-14823,-12338,-19412,-516,-14527,6209,11369,12343,18372,11136,-8844,15963,12194,12863,352,-3911,932,19855,-1760,1582,3047,19942,15541,-9546,10888,-19901,2208,13005,6209,-11636,-9385,-14842,3135,14370,-1867,4359,11118,14559,-11432,8041,-17623,-8234,8526,-3630,-2328,-5249,6459,-1228,15233,9079,1967,-7570,-10208,-4607,-18786,-8133,-2689,-10510,-8290,5871,4110,19997,-15373,-3223,15082,31,16580,19445,-8625,-13902,563,18675,-8786,-10333,16538,-10187,8547,9519,-6153,3882,5856,8888,-3421,-5138,854,2753,-4262,9691,5063,14578,-7848,-5054,-15810,-18044,12625,-14412,3328,-566,-19445,11381,3560,-5192,-6656,-7173,-15055,12891,9686,-19568,18826,10318,1468,-16674,-16909,15291,17799,5046,10612,19375,17086,-10253,15491,-6985,-4277,-16787,-16594,11732,-14766,-5306,11835,-18847,-10274,2856,5419,5852,14133,-3833,-13140,1620,10796,10005,6078,9813,15761,-14294,983,-13258,13076,1608,-1741,8267,-12633,10641,15283,17260,15384,-1784,12756,-7642,18413,11414,-17334,-15308,15784,-312,609,-11931,-7313,-12871,-12530,1206,-5250,12766,18211,9164,-3788,-12276,-19227,6,-12363,14720,-15384,-8519,-15815,-13884,-2352,10218,-11789,-5998,-9599,17076,-8880,-18821,-16235,5221,7965,-12857,13865,7218,-17504,-5725,743,1735,-12453,1333,-19352,8745,10987,-15045,-2083,13711,-12331,9407,14446,8538,17810,1143,-18733,10340,605,12922,18915,536,8409,6167,16435,-10055,7554,9507,-15106,12534,13059,-6382,900,-2175,-1139,-14227,5575,12791,-9641,9220,-8166,5816,10594,19660,5069,-8561,9443,-9302,-3421,-17841,2409,5116,-6415,7066,14230,12,-9552,10898,-10097,-19818,-13256,-16487,-11983,1789,3823,-11624,-9337,-7308,1314,13718,-11968,-6123,8151,-12878,10413,17771,1023,16955,-18942,7558,-6061,3179,-6256,-7347,-7415,-11644,12484,-3941,-7674,-14502,19686,-5104,-5867,-7560,11337,14538,-16531,17245,-14487,99,11925,-1037,3409,10770,18593,12227,3664,25,14870,15167,688,-4934,7135,8382,-19761,-5987,15899,-5284,15005,-11621,-6469,1634,15287,-2442,-17387,6614,14545,11393,6167,13038,6065,-16801,-3349,-19842,13903,-4557,7903,-9232,7855,-14485,16301,3713,-17675,-11570,-2815,-19367,3108,-2278,9157,5853,-16279,-3446,3638,-2186,-9262,12883,-8415,17380,4643,-12074,13422,14476,3245,19152,-15663,11470,14773,5380,13324,-6534,-18981,15267,-4825,-14652,8218,18253,1413,11048,10764,-16244,16089,-17674,-10245,-15123,-3726,-16150,-5224,-7981,13190,-9982,5563,9432,-9400,8817,17004,-9057,1045,16767,11065,-14602,-4156,-16822,-11155,-1856,2581,7314,11949,-16295,-1351,-3011,4912,-7981,18368,-8307,8481,12784,-1068,5601,-7088,-9201,4132,282,18170,-16144,16736,12122,-16138,-14004,-5277,-14955,-6716,-4146,8505,14759,5682,-11855,-6740,-11916,15756,19561,-1234,-16565,10428,-13472,-1401,15549,-15929,9951,-11993,-9814,5290,-18088,-5358,10303,15560,-156,-3079,-14829,10476,-8946,6663,994,8290,12197,-14592,9857,13844,17884,3182,14496,-12909,9494,-5112,3294,10035,8784,-13844,-2307,-5974,-12193,-7825,-11171,-14959,2920,-18460,-8188,-4611,3803,16301,-6833,-14612,-17693,6023,-13814,12642,17243,-19097,-2091,-1683,-19119,-14570,19422,-16219,-17702,-5763,-13763,13678,-5577,5829,6431,-14134,-18064,16144,-6420,-4808,-6087,-3267,6548,19595,-3091,2826,4876,-16873,-4081,8651,8791,-13369,13556,-17515,-6997,7150,7075,-8192,-9536,2369,6351,13236,-7110,7898,7115,-15394,-11876,-8618,2680,1100,17947,-6188,15320,4803,-2765,-3816,-7284,-16724,5952,-590,1977,7282,14247,-9906,18013,4797,18645,1037,-18236,4876,-2250,6386,-1646,8586,-18385,-13849,10046,10620,-11820,8372,-7583,-198,-9411,-16637,15697,-19343,-12429,-6705,19857,18528,-8393,1452,4738,-2476,-7959,-13509,5959,5716,11369,2565,-8890,-15231,11427,4880,3860,-4834,13145,5796,-15990,-9649,-11957,318,-16671,5982,-8409,3566,15669,2944,-19958,14248,6441,7889,-16644,-192,11582,11534,-10229,-14136,18303,-11306,-6568,-10566,4690,3998,8380,-13356,18592,4339,7663,-5999,-3077,-10648,-3650,18304,4743,-19669,-17412,-1392,18795,7361,-13853,5756,14195,7682,-765,-7113,-15208,-19944,11828,9462,-12402,7061,-52,-19182,-3537,18879,-11024,-6336,-4267,-7668,19914,-19409,6779,-10995,-7896,4800,-1010,-18527,16168,-19383,-7204,9276,-19597,571,11996,11306,-4462,2283,-15053,-19879,-5648,12621,-11756,10781,6768,1847,3047,15344,2566,9039,-18796,-12842,-17498,-17419,8861,4705,4204,432,-1170,8765,-10140,12462,-12842,-18857,-13927,13366,2535,12338,-18813,-8406,-4431,14040,-3332,-9935,-3923,2480,12103,-16197,12760,6007,5988,-19018,-11341,-16222,186,6795,5506,10862,3477,5352,3442,19409,-3121,19960,13853,-4873,1928,-9316,8799,14378,11655,-9844,155,12276,1125,-4522,12960,-4241,5306,5061,-12379,4190,17921,-7873,-12306,167,-13350,15773,-8380,7374,10135,-3365,14375,-18584,-4171,7991,1228,2435,-887,19077,5226,3461,7319,-9653,-13179,16413,-15835,15464,12024,-3418,765,-10208,9764,-10373,-14998,4080,-13631,5969,16520,3196,-2360,13947,-19472,-10407,7692,-3796,-14113,-6302,2561,19235,-12780,-7360,16061,172,11965,-7398,7235,-12682,-4105,-7202,-13825,-6980,-11405,17747,11897,6536,2362,13240,-14578,19672,-9658,-13384,-15980,835,-2270,-6842,7735,-17845,9228,9242,-1440,-15220,10255,-19797,-6113,3602,16087,-9410,7718,-15603,14941,-6208,2651,-843,-3066,4264,12641,-18398,-3196,-12555,-11965,-4922,10903,2935,-2204,-1400,-18538,12521,-6808,-13421,-8763,-2464,-13584,-15195,17682,-6820,-7230,3233,11609,-10096,19082,-621,-3669,11295,250,17900,-9238,10334,-10717,-739,14372,6159,11931,19729,-15975,-12149,1314,-11422,9986,-4376,10047,9067,-15413,15588,15176,537,10580,-1415,-10672,10387,-9370,17150,3823,10474,-14136,-7124,9004,-1054,-12769,4019,-15501,2328,-15829,-4865,-17135,15209,10520,936,10864,464,-4992,592,-10675,3079,13921,8829,-9355,-11186,-4730,9296,-4196,-7400,15783,14539,-18144,13275,8097,12408,5863,12489,10486,-9983,-9604,16030,-15590,8129,6301,1512,6626,-16987,3459,12449,-11829,17339,-15050,-19621,-9915,13686,16805,-18241,7399,-1600,16620,-9797,15788,-16809,7860,-11210,-14315,8427,-11155,-8675,7561,-13509,6583,1674,-4488,-16166,-10665,-14639,-13597,-18172,16511,5173,13647,-13339,-5727,-9808,-4765,-15407,10270,1584,-17269,-13035,18654,-6424,7741,17651,-5526,2203,16282,10640,2027,-2789,8476,-9863,-1687,-13960,-8498,3411,-8897,-2749,16012,4830,10011,13377,7906,9357,-4430,15510,-5490,2660,1298,-16258,-10686,-7739,-8275,11664,10767,-13537,-13153,-14408,-11957,6708,10506,17915,6181,9002,-18124,13944,6346,-14458,19618,19587,18708,-19547,-7058,11479,7240,-13794,-10672,4225,-3328,1012,13988,-9021,19353,-15330,-1008,-1738,18539,-15437,-9669,16289,2644,15095,5536,3601,301,-1452,7068,1247,13544,19946,5259,13558,-13024,-16496,9646,5653,52,12011,6472,-16349,-16135,19715,-4372,-4470,19236,-8837,-5701,6024,-16243,4741,-11718,14687,-8487,-10800,4121,-202,-3561,19181,18345,2541,19268,-3175,4216,-9135,-16489,-1101,6829,-7817,13437,3405,10591,8191,-9523,12491,6098,-2887,-12956,7651,-224,7974,-6348,11323,7219,1104,6556,8154,6975,10492,-19501,-8976,-16543,16768,17906,-18761,-9382,6577,11298,16807,16990,-7284,-5139,-15003,-1919,-334,7015,7720,1165,19995,-12110,-6248,7589,-2554,-6337,-17214,11815,1922,10622,-16358,368,-8367,9555,-9258,-9575,-17972,-15961,16078,-19732,10664,8060,-11340,-14640,-15655,846,-1804,2352,17072,17050,-12980,-19082,-18493,11422,626,-9098,19332,-365,5495,-11973,16782,-14595,-2620,18718,-432,-13481,-16552,14484,9943,14610,-11855,-267,10665,-18611,-7205,-10225,-411,12812,-10881,-11797,16338,10721,14392,2014,-7382,819,-7868,-15186,-11350,8261,7124,19486,-12550,-4227,17901,1251,-11847,-755,-11961,1900,-15831,-14017,1176,15502,5104,826,4953,14872,-3368,8919,6016,-18033,-18489,5751,4722,1075,-12055,7094,12374,-1506,12710,4721,3653,-10257,-7709,-2213,17398,2900,-9727,15259,-3883,-6185,-15503,17846,5462,18890,-31,-14183,-10346,10710,12368,324,3808,-3907,-1567,2286,-19945,-1077,6131,11741,-15450,15066,-10562,-12270,-1751,16899,374,-14688,11616,7005,3793,4346,-13227,-1628,5377,-14693,-15296,2535,-3358,9983,8701,18499,-11393,7936,-18,5006,-9393,-9609,-18689,-13326,6324,3861,-18518,13685,-13858,-12961,-12645,3677,-2486,8518,-3494,8301,19880,-3389,-3997,-17145,7349,17967,8601,-15183,-988,-9281,19443,16615,6675,14079,3509,-19702,3755,-12497,3230,1349,15306,14350,-10152,12176,-5919,17701,18663,15397,-5427,1838,14336,-14874,19010,18989,-17846,-1150,-15657,15885,13300,16793,19556,-433,-3649,3673,-7557,-4891,3426,-18437,9305,-4885,-10866,13407,-13271,-12457,12227,-2622,17794,-19917,12489,-10060,10388,10731,11358,-10290,14406,-5847,-16052,476,-15710,15548,11005,11197,5598,14685,-15221,-16521,-16068,-6183,12744,-10509,-18937,12606,-11077,-16262,-11012,658,8816,4974,14284,-19355,-5228,19487,-6166,-2824,17272,-18169,4061,17802,-4919,-466,9149,-385,6204,-8727,14224,17779,3421,10,-7109,-9290,-11524,4414,-17081,16351,-18212,-3419,8669,3423,-3561,-18798,-6740,18780,-4210,10134,1670,17991,19402,-6506,-16193,1810,-8541,12061,-12111,14453,-10012,-1027,-4969,9116,-8716,18250,-18306,-4160,11222,1821,9069,7004,10749,7214,2158,-11785,16046,-16464,-6922,12434,4389,-14720,-4724,8658,18419,-18361,-11228,6488,-15265,-10562,18742,19386,-14712,-15996,1171,-277,11502,-3642,8381,-16760,15471,7879,16433,1366,-19917,4352,-4460,1499,2224,15511,9322,10443,-3672,17818,-19367,-7447,19654,-5174,-12125,3007,-4712,14732,16938,15056,-6750,12222,-9341,-2961,-9951,-17156,6080,-5633,-14206,18700,18778,-15780,10493,19759,3310,100,14136,4071,-7522,-19915,-2981,-10707,17336,17455,-13005,1147,-18767,-923,-17489,19771,-19608,-7325,13668,-4537,12975,-18154,2343,-7687,8735,5539,1860,11944,-3560,3547,9406,-16080,-19017,2966,-8109,-2968,-19872,-14222,10911,8407,-12790,16114,-9451,-9540,16249,-11771,-1602,17269,-18189,15400,-744,3474,-7093,-2171,5737,8031,-4847,11711,7312,13391,12507,12445,7048,3221,-14972,-8035,-16473,18653,-14384,15589,-14298,-10445,-8616,7121,12319,-2490,-3298,-7897,9655,-5747,-13361,7158,-186,-1217,-4141,7429,-7343,-19027,-16509,7417,16235,2989,-8243,17658,-10272,5795,13698,-4038,-5769,-9063,7457,-10831,6927,-6065,12927,-1056,-10442,-2914,-16410,19318,-14060,11791,-7633,3206,7444,-14416,13159,-14023,2780,17262,1374,6724,-11191,7726,9671,-3618,-18229,15537,-17417,6229,4083,-12816,13370,4431,-6747,9541,-15584,-16374,11234,1237,1842,11014,-6035,8733,10095,-14317,-7209,-6325,18879,-11035,2686,-19719,16754,-12793,-11803,-8497,-3346,16814,7540,-10856,-8784,-12999,8128,17442,18925,-11647,-16505,9644,16616,-13922,17910,16671,19448,-4225,-8515,-3524,11340,-9169,2693,762,9350,-13948,-4173,-7536,-691,-2214,1423,2368,14836,9130,-19476,-1879,13631,410,-10217,3610,17795,-1843,2806,-7448,990,-5476,3362,-12784,18751,-150,-1694,4520,-3735,-42,-10947,4229,1900,-10183,-2711,19384,2997,885,-16736,15628,-18820,1031,-16236,3537,16036,7395,-11751,-11704,-5571,-228,-18680,-13641,-4060,-10522,2862,-13057,-4004,-4448,6149,5957,1975,-18140,-2303,3041,13647,7449,-12267,-13189,-458,14236,2805,4414,-9524,-8358,-18135,-17861,8910,-16941,-16906,13781,-12920,12807,7068,-560,18255,3982,19253,3047,-16066,-15114,-18955,-19092,-15186,15501,-12156,16511,-8667,-7412,16398,-588,8523,-4784,-1313,19894,698,16900,-3040,10637,-9949,1505,-15844,13781,11138,7490,3129,5632,8807,-8268,-5399,16169,1173,12380,-1448,448,-19758,7169,-4058,-4111,6603,-10727,-134,-8465,-1656,4674,11298,-19292,10893,856,-11041,17917,-5405,17353,-18501,-19417,-4804,2438,-7815,-1708,6083,10211,18756,10694,-19767,16763,10200,-6934,-18918,886,2307,-11491,13302,8141,13540,15640,19987,4128,15182,19884,-13905,-1239,10638,-15912,-14714,-8138,-12772,-1917,4468,-16632,2437,1087,5181,-13468,10004,-17418,-16725,16399,1684,11118,4497,10108,-14263,-5924,-15695,4035,-4675,-19370,-19509,-1146,7231,-10985,7771,-4487,2465,-15313,15740,11421,12077,12173,-9232,-5934,1829,4092,2103,-588,6107,-13938,-10791,-17463,15363,-10718,-3161,10443,-3207,-9182,-14776,15279,10516,-7171,5281,9477,-9093,486,-377,-9146,15735,14501,6830,16479,-1588,-453,-13893,14026,9115,19150,-15058,-1786,-15499,-6902,-12710,-1138,13648,-5341,-17072,13333,10616,-4700,-5519,-18651,-15796,-1184,17604,-18757,-3919,15267,-1842,10300,-2868,-4180,-18166,-2704,-5073,-8912,-15130,14127,2353,-19155,-1537,19291,-766,-6726,-13762,2527,-10363,17627,-18180,-9457,-14295,-2064,1289,14213,-14234,7517,9670,12033,-15742,13617,-16462,-16353,19504,19914,12028,-8517,19374,-16347,16008,-1672,9859,16192,12471,-9271,-9408,15797,6478,-12447,17505,-7453,-167,-6158,-8083,-4410,3947,6221,4584,-11747,7853,18218,-5179,8962,10499,14641,-17715,16619,-17955,8641,-13138,-9904,-4175,14997,-3859,-19817,-12231,15308,-13230,-5920,19186,19625,-16910,9226,-19099,2049,599,1909,-17160,1747,-3755,-1704,5624,-3919,8068,-16400,3604,11662,-15352,-12502,10874,10797,657,9683,6397,4080,2301,-11891,-16255,-17164,16414,-12208,-5650,-9809,1517,13572,-1177,-7732,11792,5627,-13243,2928,-18252,-3291,13087,-10835,3973,3129,11613,-8564,-9277,13748,-15793,2068,10892,5988,-5277,-19774,16697,11312,-18841,-11410,-2760,18671,11296,-17029,-17124,13288,-17520,-8726,8512,12398,-4981,18539,-3973,9851,-9116,15360,-12186,7307,-12882,-17992,4139,-165,-11506,8613,-5289,-9556,2947,16627,621,1977,-11845,13611,-9270,17961,-11477,14610,13162,15381,8773,-13061,6352,-1548,5559,16370,-15260,6903,-6666,9829,-18315,14919,-17220,3108,-2972,10352,1489,12334,-5473,-17342,-14800,2595,-2003,19512,-16929,16201,-11629,15963,7311,-15236,12061,-16662,-15474,2960,-17516,17830,-12420,-7706,7534,5235,19138,-9005,4618,-7947,17301,-5093,7546,-6589,-5481,19994,-15823,-13523,-18552,-13963,766,-5353,6785,4276,4701,8366,9288,-17673,-17195,-18493,14860,-5428,-6719,-2011,9700,12551,12575,10779,-10722,-16362,-8089,18011,-17308,-12083,17604,-6572,-17401,10213,14163,18514,-17687,-18712,10985,2052,17733,14730,-1711,9533,14359,-9692,5079,-1162,9431,-4389,-2217,14274,16008,-18615,18692,-6784,7257,19462,-10665,9212,-4272,6895,-13211,-17097,9470,5725,-11569,-415,-928,-18397,-10124,-15710,3566,-8022,-9262,-13460,1059,4681,-7536,-17869,463,7143,8860,220,5567,-15520,973,-16197,12513,-3203,-17194,-18816,-13616,-9542,-11818,7450,19994,-13407,19679,789,-3823,6686,-14096,-16957,-14558,13684,13995,21,-3372,-13536,1118,15040,-16177,-4731,6094,-13836,-10101,14428,15756,2789,-5357,-12012,19191,18593,11459,7590,-7810,-941,18109,1953,-4363,5846,-10655,17006,6241,5600,12580,-13347,-14281,-4432,-2760,6220,-5278,-19866,14679,10291,-3072,18555,6287,-4439,13884,-16744,13028,2073,-10635,-17018,5076,-11208,-18730,-15496,-9279,7056,-18209,6819,8072,4973,19805,-6014,-11026,7809,2642,-8671,-10501,-12278,18375,8572,9527,19918,8063,10897,9076,12485,15627,18809,7300,-5119,-3941,-7584,3465,7640,14982,-16947,-11462,-19163,14489,3691,-4248,3433,17214,5111,539,9561,-6788,-18072,2315,4519,-6873,7278,-3422,8450,-16974,-428,13986,-15469,15125,-4945,-3890,1358,-8462,-4682,-6879,-15188,-11032,18697,-2932,-18045,-6192,-17037,4913,-7255,-7766,6947,7923,16112,719,5050,-12963,15484,-17422,-17110,-16427,-9754,19715,1078,-18462,2286,13530,18040,-6124,-3794,16083,-3548,-18406,15369,-4193,12427,1047,1254,-17257,-12767,609,16964,12212,-3943,6755,15479,-11785,5187,-541,-18911,-14607,8832,-7162,-18108,-1929,-11272,-11514,-7006,-14670,8962,1197,-14728,304,3784,-19021,1218,8657,-10176,-4167,15554,-2605,18940,-878,13450,11921,2643,5596,-852,-3199,-19836,-881,8024,-6405,1549,12878,1283,17238,-14540,-5104,1673,-5868,9028,-17168,-6331,13204,-18456,-491,-15641,-15461,11735,-298,18071,10544,-4218,11621,13081,-19099,-10454,16680,-1046,939,14256,11790,7560,16934,3983,-15690,185,-1927,-5782,2846,-8244,-19065,-14135,13118,-2041,-11442,19834,-7292,16662,-13806,-19404,-8793,3713,-10685,2999,-18157,-15387,5790,-5180,-11785,2253,-14048,-2227,-12499,-6500,2892,-15058,3253,-4590,16847,6273,-9968,-7114,-125,-1909,-9777,1326,-13201,-4206,-13720,14198,-17287,-7610,9812,5113,19378,3097,4968,-1402,-1556,8867,12701,2485,5146,-7801,1702,4013,-416,-5331,19442,-19221,1992,4273,-4725,5936,-12649,-11662,-5765,2405,9412,16843,13441,-8081,-3835,18424,-18660,2453,13606,-9685,17407,-4968,11789,1623,-5351,-10617,9795,8101,3364,-13792,-10369,15850,-15835,14633,8694,6917,-4623,8170,-17025,-2267,19542,9961,6913,15204,-1900,2965,-4173,16364,16222,8509,-2667,-12561,18823,724,8719,-15851,-17774,12254,-13242,-4322,13202,14598,17339,8156,11835,-8527,-14215,981,-16428,7900,18069,2175,-3541,-218,-465,-18561,15687,5454,13072,9367,-14519,1198,-4891,11152,4186,8587,958,14339,-13779,-8804,15808,-4268,-15531,-9947,-4916,17980,18454,-10340,-10381,-17312,-15628,-12121,8441,576,13804,-12242,-3611,-18884,17287,-7116,-17202,-14520,2043,7679,-16896,1212,9601,-11022,6721,8612,5706,-6430,-12435,10969,8932,-15291,-7995,144,12576,-10494,-9746,-8016,4549,-14966,781,-10625,2117,-14577,-6308,1078,-17034,19779,3281,-10806,-2959,10670,14877,-16548,-2628,-7124,12610,18980,-6520,7749,16275,-4558,-19951,-3657,-12490,-10206,-4403,-19098,-29,-19138,-4638,12435,18323,11382,-17282,-8142,12328,-1670,9019,16944,-18859,4254,12083,-251,7081,10356,-2904,2737,19487,-10427,-8425,-4040,5587,6783,-11470,10161,-15016,13321,-9392,12221,-836,2842,-10623,-5445,-7626,-10702,13052,1008,-175,153,457,4534,5445,19157,9135,7170,14336,15399,-16760,-7796,19350,13900,15629,-14040,6148,6128,18875,11915,11475,12886,12521,-11181,3763,-17558,17919,17041,-5845,-12305,4692,10070,438,-15011,-19987,-7123,-14656,2266,-16661,15734,-18988,-10173,-13865,-12268,-4666,19902,-16105,-4686,-17380,-18893,-10438,6377,-1147,-13780,-18334,14300,-12197,15656,-17571,-15965,540,-2234,517,-17832,3597,-19799,16383,-17155,307,86,-4644,16525,-8460,-4762,19712,235,7892,2408,-17555,19261,-13404,12608,11441,-5004,-1641,-5711,17764,-12750,-4153,17965,9358,9806,-4816,-12708,-1562,7677,15706,-510,18905,-1801,9312,-14054,2116,-11354,-15244,-666,3807,2924,17073,-16741,-5927,-1791,9108,-14900,3700,-1936,13850,800,15024,-10071,-37,5224,-9693,13279,-18393,-13887,-5336,-6057,-11000,-13835,9298,8389,-18953,-15935,15886,-10232,-14567,-4560,-17180,-5223,-2896,-13328,-8650,-8166,-9336,15354,16790,-333,3328,2990,-5637,-9595,11882,19081,6092,2114,-14908,-16905,5436,-19664,-15365,7508,8463,19431,359,3276,-14522,-12861,-11818,4699,2368,-3557,-4477,-15504,-14562,-766,15790,-2628,1541,-2731,15155,-4629,19167,-18515,-18940,5009,-14583,10193,-19797,11575,12483,-18579,-3478,16882,-5377,-8846,3373,-8651,-8833,-11572,13982,-4442,4322,-10520,-17052,-17159,2207,-9989,-9986,-9175,-7168,-7452,9322,18902,-4215,16299,-13263,388,15223,17325};
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	QuickSortNonR(a, 0, sz - 1);

	PrintArray(a, sz);
}

void MergeSortTest()
{
	int a[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 10, 20, 30, 12, 21 };
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	MergeSort(a, sz);

	PrintArray(a, sz);
}

void MergeSortNonRTest1()
{
	int a[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 10, 20, 30, 12, 21 };
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	MergeSortNonR1(a, sz);

	PrintArray(a, sz);
}

void MergeSortNonRTest2()
{
	int a[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 10, 20, 30, 12, 21 };
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	MergeSortNonR2(a, sz);

	PrintArray(a, sz);
}

void HeapSortTest()
{
	int a[] = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 10, 20, 30, 12, 21 };
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	HeapSort(a, sz);

	PrintArray(a, sz);
}

void CountSortTest()
{
	int a[] = { 3,-1 };
	//int a[] = { 3, 2, 1 };
	int sz = sizeof(a) / sizeof(a[0]);

	
	CountSort(a, sz);
	PrintArray(a, sz);
}

int main()
{
	//TestInsertSort();
	//BubbleSortTest();
	//SelectSortTest();
	//ShellSortTest();
	//QuickSortTest();
	QuickSortNonRTest();
	//MergeSortTest();
	//MergeSortNonRTest2();

	//HeapSortTest();
	//CountSortTest();
	return 0;
}